An Alternate Construction of an Access-Optimal Regenerating Code with Optimal Sub-Packetization Level

摘要

Given the scale of today's distributed storage systems, the failure of anindividual node is a common phenomenon. Various metrics have been proposed tomeasure the efficacy of the repair of a failed node, such as the amount of datadownload needed to repair (also known as the repair bandwidth), the amount ofdata accessed at the helper nodes, and the number of helper nodes contacted.Clearly, the amount of data accessed can never be smaller than the repairbandwidth. In the case of a help-by-transfer code, the amount of data accessedis equal to the repair bandwidth. It follows that a help-by-transfer codepossessing optimal repair bandwidth is access optimal. The focus of the presentpaper is on help-by-transfer codes that employ minimum possible bandwidth torepair the systematic nodes and are thus access optimal for the repair of asystematic node. The zigzag construction by Tamo et al. in which both systematic and paritynodes are repaired is access optimal. But the sub-packetization level requiredis $r^k$ where $r$ is the number of parities and $k$ is the number ofsystematic nodes. To date, the best known achievable sub-packetization levelfor access-optimal codes is $r^{k/r}$ in a MISER-code-based construction byCadambe et al. in which only the systematic nodes are repaired and where thelocation of symbols transmitted by a helper node depends only on the failednode and is the same for all helper nodes. Under this set-up, it turns out thatthis sub-packetization level cannot be improved upon. In the present paper, wepresent an alternate construction under the same setup, of an access-optimalcode repairing systematic nodes, that is inspired by the zigzag codeconstruction and that also achieves a sub-packetization level of $r^{k/r}$.